﻿/*
题目: 单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

https://leetcode.cn/problems/word-search-ii/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Trie {
public:
    vector<Trie*> children;
    string        prefix;

public:
    Trie()
        : children(26, nullptr)
    {}

    void insert(const string& word) {
        Trie* it = this;
        for (int i = 0; i < word.size(); i++) {
            char ch = word[i];
            int pos = ch - 'a';
            if (it->children[pos] == nullptr) {
                it->children[pos] = new Trie();
            }

            it = it->children[pos];
        }
        it->prefix = word;
    }

    Trie* next(char ch) {
        int pos = ch - 'a';
        return children[pos];
    }
};

class Solution {
#define VIS '@'

private:
    const int dirs[5] = { 0, -1, 0, 1, 0 };

public:
    Trie* trie;
    int             n;
    int             m;

    vector<string>  res;

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        // 1. init
        n = board.size();
        m = board[0].size();
        trie = new Trie();

        // 2. build trie
        for_each(words.begin(), words.end(), [this](const string& word) { trie->insert(word); });

        // 3. dfs
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch = board[i][j];
                if (trie->next(ch) != nullptr) {
                    string tmp;
                    dfs(board, i, j, trie->next(ch), tmp);
                }
            }
        }

        return res;
    }

    void dfs(vector<vector<char>>& board, int x, int y, Trie* iter, string& tmp) {
        char ori = board[x][y];
        tmp.push_back(board[x][y]);

        if (tmp == iter->prefix) {
            res.emplace_back(tmp);
            iter->prefix = "";          // 匹配成功之后置为空，防止重复匹配
        }

        board[x][y] = VIS;
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i];
            int ny = y + dirs[i + 1];

            if (!ok(nx, ny) || board[nx][ny] == VIS) continue;

            Trie* next = iter->next(board[nx][ny]);
            if (next != nullptr) {
                dfs(board, nx, ny, next, tmp);
            }
        }

        tmp.pop_back();
        board[x][y] = ori;
    }

    bool ok(int x, int y) {
        return x >= 0 && y >= 0 && x < n&& y < m;
    }
};